#include "student.h"
#include <iostream>

heap::heap(){
    data=NULL;
    length = 0;
}

heap::heap(Student *datahead, int l){
    length=l;
    for(int i = PARENT(l-1); i>=0; i--)
    shiftdown(datahead, i);
}

heap::~heap(){
    delete[] data;
}

int heap::get_height(){
    int l=length;
    int dights=1;
    while((l >>= 1) != 0)
    dights++;
    return dights;
}

int heap::shiftdown(Student *datahead, int i){
    int lc = LEFTCHILD(i);
    if(lc >= length)
    return 0;
    int child = lc;
    int rc = RIGHTCHILD(i);
    if(rc < length && datahead[rc].out_maj() > datahead[lc].out_maj())
    child = rc;
    if(datahead[i].out_maj() < datahead[child].out_maj())
    {
        Student temp = datahead[i];
        datahead[i] = datahead[child];
        datahead[child] = temp;
    }
    shiftdown(datahead, child);
    return 0;
}

int heap::sort(Student *datahead){
    int l = length;
    while(length > 1){
//      int tmp = data[0];
        Student tmp = datahead[0];
        datahead[0] = datahead[length-1];
        datahead[length-1] = tmp;
        length--;
        shiftdown(datahead,0);
    }
    length=l;
}

int heap::printout(Student *datahead){
    for(int i =0; i<length; i++){
        std::cout << datahead[i].out_maj() << ",\t";
    }
    std:: cout << "\b\b\n";
    for(int i =0; i<length; i++){
        std::cout << datahead[i].out_num() << ",\t";
    }
    std:: cout << "\b\b\n";
    for(int i =0; i<length; i++){
        std::cout << datahead[i].out_gpa() << ",\t";
    }
    std:: cout << "\b\b\n";
    return 0;
}

merge::merge(){
    length=0;
}

merge::merge(Student *arr,int l){
    length=l;
    sort(arr,0,length-1);
}

int merge::sort(Student *arr, int n1, int n2){
    if(n1<n2){
        int r=(n1+n2)/2;
        sort(arr,n1,r);
        sort(arr,r+1,n2);
        unify(arr,n1,r,n2);
    }
    return 0;
}

int merge::unify(Student *arr, int left, int centre, int right){
    Student oneside[centre-left+1],anotherside[right-centre];
    for(int i = 0; i+left<=centre; i++){
        oneside[i]=arr[i+left];
        if(i<right-centre)
        anotherside[i]=arr[i+centre+1];
        }
    int i=0,j=0,k=0;
    while(i+left<=centre&&j<right-centre){
        if(oneside[i].out_gpa()<=anotherside[j].out_gpa()){
            arr[left+k]=oneside[i];
            k++;i++;
        }
        else{
            arr[left+k]=anotherside[j];
            k++;j++;
        }
    }
    for(i;i+left<=centre;i++)
    {
        arr[left+k]=oneside[i];
        k++;
    }
    for(j;j+centre<right;j++){
        arr[left+k]=anotherside[j];
        k++;
    }
    return 0;
}